package offer.day25;

import java.util.ArrayList;

public class No40GetLeastNumbers_Partition {
    /*
     * 面试题40：最小的k个数
     * 题目：输入n个整数，找出其中最小的k个数。
     * 例如，输入4，5，1，6，2，7，3，8这8个数字，则最小的4个数字是1，2，3，4.
     *
     *
     * 思路：
     * 方法一：最简单，将数组由大到小排序   前k个数就是最小的k个数   时间复杂度O(nlogn)
     * 方法二：只有当允许修改输入的数组时才能使用，时间复杂度O(n)
     * 			根据No39中数组中超过一半的数字的partition的方法，
     * 			可以知道第k个元素的左边就是比k小的k个元素，所以根据这种思想可以得到与partition类似的算法
     * 方法三：若不允许修改原数组时使用，适用于处理海量数据，时间复杂度O(nlogn) 空间复杂度O(1) 数据不会乱序
     *
     *
     *
     * */
    public static void main(String[] args) {
        No40GetLeastNumbers_Partition g = new No40GetLeastNumbers_Partition();
        int[] array = {9, 8, 7, 5, 3, 4, 6, 2};
        int length = 8;
        int k = 4;
        ArrayList<Integer> result = g.GetLeastNumbers_Partition(array, k);
        System.out.println("输出数组中最小的" + k + "位数：");
        System.out.println(result);
    }

    private ArrayList<Integer> GetLeastNumbers_Partition(int[] array, int k) {
        if (array == null || array.length == 0 || k <= 0 || k > array.length) {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list=new ArrayList<>();
        int low = 0;
        int high = array.length - 1;
        int p = partition(array, low, high);
        while (p != k - 1) {
            if (p < k - 1) {
                low = p + 1;
            } else {
                high = p - 1;
            }
            p = partition(array, low, high);
        }
        for(int i=0;i<k;i++){
            list.add(array[i]);
        }
        return list;
    }

    private int partition(int[] array, int low, int high) {
        int val = array[low];
        int i = low + 1;
        int j = high;
        while (i <= j) {
            while (i <= high && array[i] < val) {
                i++;
            }
            while (j >= low && array[j] > val) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(array, i++, j--);
        }
        swap(array, low, j);
        return j;
    }

    private void swap(int[] array, int indexA, int indexB) {
        int temp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = temp;
    }
}
